package me.mingshan.sort;

import java.util.Arrays;

public class InsertSort2 {
    public static void main(String[] args) {
        int[] a = {1,3,4,5,3};
        t(a);
        System.out.println(Arrays.toString(a));
    }

    private static void t(int[] a) {
        if (a == null || a.length < 2) {
            return;
        }

        // 外层，代表前面多少个已经排好序了
        for (int i = 0; i < a.length - 1; i++) {
            int nextIndex = i + 1;
            if (nextIndex == a.length) {
                break;
            }

            int nextValue = a[nextIndex];
            // 当前数所在的位置
            int l = nextIndex;
            // 内层循环从第i+1开始，往前循环，找到比当前数还小的，如果大直接停止
            for (int j = nextIndex - 1; j >= 0; j--) {
                if (a[j] > nextValue) {
                    swap(a, l, j);
                    l = j;
                } else {
                    break;
                }
            }
        }
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}
